% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%
\begin{document}
%
\frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
\addtocmark{Solving Difficult LR Conflicts} % additional mark in the TOC
%
%\chapter*{Preface}
%
%\chapter*{Organization}
%
%\section*{Sponsoring Institutions}
%
%Bernauer-Budiman Inc., Reading, Mass.\\
%The Hofmann-International Company, San Louis Obispo, Cal.\\
%Kramer Industries, Heidelberg, Germany
%
%\tableofcontents
%
\mainmatter              % start of the contributions
%
\title{
Solving Difficult LR Parsing Conflicts by Postponing Them%\footnotemark[3]
}
%
\titlerunning{Solving Difficult LR Conflicts}
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{
L. Garcia-Forte
and
C.~Rodriguez-Leon
}
%
\authorrunning{C.~Rodriguez-Leon and L. Garcia-Forte}
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Ivar Ekeland, Roger Temam, Jeffrey Dean, David Grove,
Craig Chambers, Kim B. Bruce, Elisa Bertino}
%
\institute{
Departamento de EIO y Computaci\'on,\\
Universidad de La Laguna, Tenerife, Spain\\
\email{casiano@ull.es},\\ WWW home page:
\texttt{http://nereida.deioc.ull.es}
}

\maketitle              % typeset the title of the contribution

\hyphenation{spe-cu-la-ti-ve spe-ci-fi-ca-tion a-llo-wing
con-flicting am-bi-guous in-vol-ved}

\begin{abstract}
Though yacc-like LR parser generators provide ways to solve shift-reduce
conflicts using token precedences, no mechanisms are provided
for the resolution of reduce-reduce conflicts. To solve this kind
of conflicts the language designer has to modify the grammar.
All the 
solutions for dealing with these difficult conflicts branch at each alternative,
leading to the exploration of the whole search tree. 
These strategies differ in the way the tree is explored:
GLR, Backtracking LR, Backtracking LR with priorities, etc.  This
paper explores an entirely different path:  to extend the yacc
conflict resolution sublanguage with new constructs allowing the
programmers to explicit the way the conflict must be solved.
These extensions supply ways to resolve any kind of conflicts, including
those that
can not be solved using static precedences.
The method makes also feasible the parsing of
grammars whose ambiguity must be solved in terms of the semantic context.  
Besides, it brings to LR-parsing a common LL-parsing feature:
the advantage of providing full control over the specific trees
the user wants to build.
\end{abstract}
%
\section{Introduction}
Yacc-like LR parser generators \cite{Johnsonyacc} provide ways to solve shift-reduce mechanisms
based on token precedence. No mechanisms are provided for the resolution
of reduce-reduce conflicts or difficult shift-reduce conflicts. 
To solve such kind of conflicts the language designer 
has to modify
the grammar. Quoting Merrill \cite{merrill}:
\begin{quote}
\begin{it}
Yacc lacks support for resolving ambiguities in the language for 
which it is attempting to generate a parser. It does a simple-minded approach
to resolving shift/reduce and reduce/reduce conflicts, but this 
is not of sufficient power to solve the really thorny problems
encountered in a genuinely ambiguous language
\end{it}
\end{quote}

Some  context-dependency ambiguities can be solved through the use of lexical tie-ins: a flag
which is set by the semantic actions, whose purpose is to alter the way
tokens are parsed. 
But it is not always possible or easy to resort to this kind of tricks 
to fix some context dependent ambiguity.
A more general solution is to extend 
LR parsers with the capacity to branch
at any multivalued entry of the LR action table. For example, Bison \cite{bison},
via the \verb|%glr-parser directive| 
and Elkhound \cite{elkhound}
provide implementations of the Generalized LR (GLR) algorithm \cite{tomita2}.
In the GLR algorithm, when a conflicting transition is encountered, 
the parsing stack is forked
into as many parallel parsing stacks as conflicting actions.
The next input token
is read and used to determine the next transitions for each of the
top states. If some top state does not transit for 
the input token it means that path is invalid and that branch
can be discarded. 
Though GLR has been successfully applied to
the parsing of ambiguous languages, the handling 
of languages that are both context-dependent and ambiguous 
is more difficult. 
The Bison manual \cite{bison} points out the following caveats when using GLR:

    \begin{it}
    \begin{quotation}
\ldots there are at least two potential problems to beware. First, always analyze
the conflicts reported by Bison to make sure that GLR splitting is only
done where it is intended. A GLR parser splitting inadvertently may cause
problems less obvious than an LALR parser statically choosing the wrong
alternative in a conflict. Second, consider interactions with the lexer
with great care. Since a split parser consumes
tokens without performing any actions during the split, the lexer cannot
obtain information via parser actions. Some cases of lexer interactions
can be eliminated by using GLR to shift the complications from the lexer
to the parser. You must check the remaining cases for correctness.
    \end{quotation}
    \end{it}


The strategy presented here 
extends yacc conflict resolution mechanisms
with new ones, supplying ways to resolve conflicts
that can not be solved using static precedences. 
The algorithm for the generation of the LR tables remains unchanged,
but the programmer can modify the parsing tables
during run time. 

The technique involves labelling the points in conflict in the grammar specification
and providing additional code to resolve the conflict when it arises.
Crucially, this does not requires rewriting or transforming the grammar,
trying to resolve the conflict in advance, backtracking or branching into concurrent
speculative parsers. Instead, the resolution is postponed until the conflict actually arises
during parsing, whereupon user code inspects the state of the underlying parse
engine to decide the appropriate solution. There are two main benefits:
Since the full power of the native universal hosting language is at disposal,  
any grammar ambiguity can be tackled.
We can also expect - since the conflict handler is written by the programmer - 
a more efficient solution which
reduces the required amount of backtracking or branching.


This technique can be combined to complement both GLR and backtracking LR
\mbox{algorithms \cite{kelbt}} to give the programmer a finer control of the branching process.
It puts the user - as it occurs in top down parsing - 
in control of the parsing strategy when the grammar is ambiguous,
making it easier to deal with efficiency and context dependency issues.
One disadvantage is that it requires a comprehensive knowledge of LR parsing.
It is conceived to be used when none of the available techniques - static precedences,
grammar modification, backtracking LR or Generalized LR - produces satisfactory solutions.
We have implemented these techniques in 
\verb|Parse::Eyapp| \cite{Rodriguez:Leon},
a yacc-like LALR parser generator for \mbox{Perl \cite{Wall:Perl,perl6}}. 
The Perl language is, quoting Paul Hudak's \mbox{article \cite{hudak}} a ``{\it domain specific language for text manipulation}".

This paper is divided in six sections.
The next section introduces the Postponed Conflict Resolution
(PPCR) strategy.
The following three sections illustrate the way the technique
is used. 
The first presents an ambiguous grammar where the disambiguating rule is made in terms
of the previous context.
The next shows the technique on a difficult grammar that has been previously used in the literature \cite{bison} to illustrate
the advantages of the GLR engine: the declaration of enumerated and subrange types in 
Pascal \cite{ISO:1990:EPI}.
The last example deals with a grammar that can not be parsed by any LL(k) nor LR(k), whatever the value
of \verb|k|, nor for packrat parsing algorithms \cite{ford}.
The last section 
summarizes the advantages and disadvantages of our proposal.
%
%

\section{The \textit{Postponed Conflict Resolution} Strategy}
\label{section:ppcrforrr}


The {\it Post\underline{p}oned Conflict Resolution} is a strategy (PPCR strategy)
to apply whenever there is a shift-reduce or reduce-reduce conflict which is
unsolvable using static precedences. It delays the decision, whether to shift
or reduce and by which production to reduce, to parsing time. 
Let us assume the \verb|eyapp| compiler announces  the presence of
a reduce-reduce conflict.
The steps followed to solve a reduce-reduce conflict using the
PPCR strategy are:

\begin{enumerate}
\item 
Identify the conflict: What LR(0)-items/productions and tokens are involved?.

Tools must support that stage, as for example via  the \verb|.output| file generated by \verb|eyapp|.
Suppose  we identify that the participants are the two LR(0)-items $A \rightarrow \alpha_\uparrow$
and
$B \rightarrow \beta_\uparrow$ when the lookahead token is \verb|@|.

\item The software must allow the use of symbolic labels to refer
by name to the productions involved in the conflict.
Let us assume that production $A \rightarrow \alpha$ 
has label \texttt{:rA} and production $B \rightarrow \beta$
has label \texttt{:rB}. 
A difference with \verb|yacc| is that
in \verb|Parse::Eyapp| productions can have {\it names} and {\it labels}. 
In \verb|Eyapp| names and labels can be 
explicitly given using the directive \verb|%name|, using a syntax similar to this one:

\begin{eqnarray*}
\mbox{{\tt \%name :rA}}& A &\rightarrow \alpha\\
\mbox{{\tt \%name :rB}}& B &\rightarrow \beta 
\end{eqnarray*}


\item
Give a symbolic name to the conflict. In this case we choose \verb|isAorB|
as name of the conflict. 

\item
\label{item:mark}
Inside the {\it body} section of the grammar, mark the points of conflict using the 
new reserved word \verb|%PREC| followed by the conflict name:

\begin{eqnarray*}
\mbox{{\tt \%name :rA\ }}    A &\rightarrow \alpha &\mbox{\tt\ \%PREC IsAorB }\\
\mbox{{\tt \%name :rA\ }}    B &\rightarrow \beta  &\mbox{\tt\ \%PREC IsAorB }
\end{eqnarray*}

\item
\label{item:handler}
Introduce a \verb|%conflict| directive inside the {\it head} section of
the translation scheme to specify the way the conflict will be solved.
The directive is followed by some code - known as the {\it conflict handler} -
whose mission is to modify 
the parsing tables. This code will be executed
each time the associated conflict state is reached.
This is the usual layout of the conflict handler:

\begin{verbatim}
%conflict  IsAorB {
  if (is_A) { $self->YYSetReduce('@', ':rA' ); } 
       else { $self->YYSetReduce('@', ':rB' ); }
}
\end{verbatim}
Inside a conflict code handler the Perl default variable \verb|$_| refers to
the input and \verb|$self| refers to the parser object.

%\begin{quotation}
Variables in Perl - like \verb|$self| -
have prefixes like \verb|$| (scalars),
\verb|@| (lists), \verb|%| (hashes or dictionaries), \verb|&| (subroutines), etc. 
specifying the type of the variable. These prefixes are called {\it sigils}.
The sigil \verb|$| indicates a {\it scalar} variable, i.e. a variable that stores a single value:
a number, a string or a reference. In this case \verb|$self| is a reference to the parser object.
The arrow syntax \verb|$object->method()| is used to call a method: it is the equivalent 
of the dot operator \verb|object.method()| used in most 
OOP languages. Thus the call
\begin{verbatim}
          $self->YYSetReduce('@', ':rA' ) 
\end{verbatim}
is a call to the 
\verb|YYSetReduce| method of the object \verb|$self|.
%\end{quotation}

The method \verb|YYSetReduce| provided by \verb|Parse::Eyapp| receives a token, like \verb|'@'|,
and a production label, like \verb|:rA|. The call
\begin{center}
\begin{tabular}{p{8cm}}
\begin{verbatim}
 $self->YYSetReduce('@', ':rA' )
\end{verbatim}
\end{tabular}
\end{center}
sets the parsing action
for the state associated with the 
conflict \verb|IsAorB| to 
reduce by the production \verb|:rA| when the current lookahead is
\verb|@|.

The call to \verb|is_A| 
represents the context-dependent
dynamic knowledge that allows us to take the right
decision.
It is usually a call to a nested parser for $A$
but it can also be any other contextual information we have 
to determine which one is the 
right production.

\end{enumerate}

The procedure is similar for shift-reduce conflicts. Let us assume we have
identified a shift-reduce conflict between LR-(0) items
$A \rightarrow \alpha_\uparrow$ and $B \rightarrow \beta\ _\uparrow\ \gamma$ for some token
\verb|'@'|.  Only steps \ref{item:mark} and \ref{item:handler} change slightly:

\begin{itemize}
\item[\ref{item:mark}'.]  Again, we must give a symbolic name to  $A \rightarrow \alpha$
and mark with the new \verb|%PREC| directive 
the places where the conflict occurs:

\begin{eqnarray*}
    \mbox{{\tt \%name :rA\ }}    A &\rightarrow \alpha &\mbox{\tt\ \%PREC IsAorB }\\
    B &\rightarrow \beta  &\mbox{\tt\ \%PREC IsAorB\ \ } \gamma
\end{eqnarray*}

\item[\ref{item:handler}'.]
Now the conflict handler calls the \verb|YYSetShift| method to set 
the \verb|shift| action:

\begin{verbatim}
%conflict  IsAorB {
      if (is_A) { $self->YYSetReduce('@', ':rA' ); }
      else { $self->YYSetShift('@'); }
   }
\end{verbatim}
\end{itemize}

\section{A Simple Example}

The following 
example\footnote{For the full examples used in this paper, see the directory {\tt examples/debuggingtut/} in
the {\tt Parse::Eyapp} distribution \cite{Rodriguez:Leon}} 
accepts lists of two kind of commands: 
{\it arithmetic expressions} like \verb|4-2-1| or one of two {\it associativity commands}:
\verb|left| or  \verb|right|. When a \verb|right| command is issued, the semantic of the 
\verb|'-'| operator is changed to be right associative. When a \verb|left| command is issued
the semantic for \verb|'-'| returns to its classic left associative interpretation.
Here follows an example of input. Between shell-like comments appears the expected output:
\begin{center}
\begin{tabular}{p{8cm}}
\begin{verbatim}
$ cat input_for_dynamicgrammar.txt 
2-1-1 # left:  0 = (2-1)-1
RIGHT
2-1-1 # right: 2 = 2-(1-1)
LEFT
3-1-1 # left:  1 = (3-1)-1
RIGHT
3-1-1 # right: 3 = 3-(1-1)
\end{verbatim}
\end{tabular}
\end{center}
We use a variable \verb|$reduce| (initially set to \verb|1|) 
to decide the way in which the ambiguity 
\verb|NUM-NUM-NUM| is solved. If \verb|false| we will set the \verb|NUM-(NUM-NUM)| 
interpretation. The variable \verb|$reduce| 
is modified each time the input program emits a \verb|LEFT| or
\verb|RIGHT| command. 

Following the steps outlined above,
and after looking at the \verb|.output| file, we see 
that the items involved in the announced shift-reduce conflict are 

\begin{eqnarray*}
expr \rightarrow expr_\uparrow - expr \\
expr \rightarrow expr - expr_\uparrow 
\end{eqnarray*}

\noindent and the lookahead token is \verb|'-'|.
We next mark the points in conflict in the grammar using
the \verb|%PREC| directive (see Figure \ref{figure:expressions})
\begin{center}
\begin{figure}[hbt]
\begin{tabular}{|p{5.7cm}|p{6.15cm}|}
\hline
\begin{verbatim}
%%
p:  
      /* empty */     {}
    | p c             {}
;

c:
      $expr { print "$expr\n" }
    | RIGHT { $reduce = 0}
    | LEFT  { $reduce = 1}
;
\end{verbatim}
&
\begin{verbatim}
expr: 
      '(' $expr ')'  { $expr } 
    | %name :M
      expr.left         %PREC lOr
        '-' expr.right  %PREC lOr
         { $left -$right }

    | NUM
;
\end{verbatim}\\
\hline
\end{tabular}
\caption{
An Example of Context Dependent Ambiguity Resolution
}
\label{figure:expressions}

\end{figure}
\end{center}

The $dollar$ and $dot$ notation used in some right hand sides (rhs)  like in \verb|expr.left '-' expr.right|
and \verb|$expr| is used to associate variable names with the attributes of the symbols. 

The conflict handler \verb|lOr| defined in the header section
is:
\begin{verbatim}
%conflict lOr {
  if ($reduce) {$self->YYSetReduce('-', ':M')} 
  else         {$self->YYSetShift('-')}
}
\end{verbatim}
If \verb|$reduce| is \verb|true|
we set the parsing action to {\it reduce} by the production labelled \verb|:M|,
otherwise we choose the {\it shift action}.

Observe how PPCR allow us to dynamically change at will the meaning of the same statement. 
That is certainly harder to do  using alternative techniques,
either problem specific, like {\it lexical Tie-Ins} \cite{bison}, or more general,
like \mbox{GLR \cite{tomita2}}. 


\section{Nested Parsing of Unexpended Input and Context}

This section illustrates the technique through a problem 
that arises in the declaration of enumerated and
subrange types in the programming language Pascal. The problem is taken from the Bison manual,
(see section `{\it Using GLR on Unambiguous Grammars}') 
where it is used as a paradigmatic example of when to switch to the GLR \mbox{engine \cite{bison}}.
Here are some cases:

\begin{center}
\begin{tabular}{p{4.7cm}}
\begin{verbatim}
type subrange = lo .. hi;
type enum = (a, b, c);
\end{verbatim}
\end{tabular}
\end{center}

The original language standard allows only numeric literals and constant
identifiers for the subrange bounds (‘\verb|lo|’ and ‘\verb|hi|’), but Extended
Pascal (ISO/IEC 10206) \cite{ISO:1990:EPI} and many other Pascal implementations allow
arbitrary expressions there. This gives rise to declarations like the  following: 

\begin{center}
\begin{tabular}{|p{5cm}|p{3.5cm}|}
\hline
\begin{verbatim}
type subrange = (a) .. b;
\end{verbatim}
&
\begin{verbatim}
 type enum = (a);
\end{verbatim} \\
\hline
\end{tabular}
\end{center}

The corresponding declarations look identical until the `\verb|..|' token. With
normal LALR(1) one-token lookahead it is not possible to decide between
the two forms when the identifier `\verb|a|' is parsed. It is, however,
desirable for a parser to decide this, since in the latter case `\verb|a|'
must become a new identifier to represent the enumeration value, while
in the former case `\verb|a|' must be evaluated with its current meaning,
which may be a constant or even a function call. The Bison  manual
considers and discards several potential solutions to the problem to conclude
that the best approach is to declare the parser to use
the GLR algorithm. 
To aggravate the conflict we have added the C {\it comma} operator
inside \verb|expr|\footnote{Perhaps the language designer wants to extend Pascal
with lexicographic ranges}, making room for the generation of declarations
like:

\begin{center}
\begin{tabular}{|p{6.8cm}|p{4.1cm}|}
\hline
\begin{verbatim}
type subrange = (a, b, c) .. (d, e);
\end{verbatim}
&
\begin{verbatim}
type enum = (a, b, c);
\end{verbatim}\\
\hline
\end{tabular}
\end{center}
which makes the parsing even more difficult.

Here is our modification of the  vastly simplified subgrammar of Pascal type declarations
found \mbox{in \cite{bison}}.  


\begin{center}
\begin{figure}[hbt]
\begin{tabular}{|p{6.4cm}|p{5.6cm}|}
\hline
\begin{verbatim}
%token ID  = /([A-Za-z]\w*)/
%token NUM = /(\d+)/

%left   ','
%left   '-' '+'
%left   '*' '/'

%%

type_decl : 'TYPE' ID '=' type ';'
;

type : 
      '(' id_list ')'
    | expr '..' expr
;
\end{verbatim}
&
\begin{verbatim}
id_list : 
      ID                    
    | id_list ',' ID
;

expr : 
      '(' expr ')'        
    |  expr '+' expr
    |  expr '-' expr
    |  expr '*' expr
    |  expr '/' expr
    |  expr ',' expr /* new */
    |  ID                     
    |  NUM
;
\end{verbatim}\\
\hline
\end{tabular}
\end{figure}
\end{center}

When used as a normal LALR(1) grammar, eyapp correctly complains about two
reduce/reduce conflicts:
\begin{verbatim}
$ eyapp -v pascalenumeratedvsrange.eyp 
2 reduce/reduce conflicts
\end{verbatim}
The generated \verb|.output| file tell us that both conflicts occur in state 11. It also give us the 
contents of state 11:
\begin{center}
\begin{tabular}{p{12cm}}
\begin{verbatim}
State 11:
    id_list -> ID . (Rule 4)
    expr -> ID .    (Rule 12)

    ')' [reduce using rule 12 (expr)]
    ')' reduce using rule 4 (id_list)
    '*' reduce using rule 12 (expr)
    '+' reduce using rule 12 (expr)
    ',' [reduce using rule 12 (expr)]
    ',' reduce using rule 4 (id_list)
    '-' reduce using rule 12 (expr)
    '/' reduce using rule 12 (expr)
\end{verbatim}
\end{tabular}
\end{center}
From the inspection of state 11 we can conclude that
the two reduce-reduce conflicts occur between productions \verb|id_list -> ID|
and \verb|expr -> ID| in the presence of tokens `\verb|)|' and `\verb|,|'.
%File \verb|pascalenumeratedvsrangesolvedviadyn.eyp|
To solve the conflict  we label the two involved productions
and set the \verb|%PREC| directives:
\begin{center}
\begin{tabular}{p{9cm}}
\begin{verbatim}
id_list : 
      ...
      %name ID:ENUM
      ID                     %PREC rangeORenum
      ...
expr : '(' expr ')'   
      ...
    | %name ID:RANGE
      ID                     %PREC rangeORenum
      ...
\end{verbatim}
\end{tabular}
\end{center}
When the conflict point is reached the conflict handler below calls the method
\verb|YYLookBothWays(|$a, b$\verb|)|. 
\begin{center}
\begin{tabular}{p{11cm}}
\begin{verbatim}
%conflict rangeORenum {
  my $s = $self->YYLookBothWays('TYPE', ';');
  if ($s =~ /^TYPE ID = \( ID ( , ID )* \) ;$/x) 
       { $self->YYSetReduce([',', ')'], 'ID:ENUM' ); }
  else { $self->YYSetReduce([',', ')'], 'ID:RANGE' ); }
}   
\end{verbatim}
\end{tabular}
\end{center}
The substring from the {\it right sentential form}\footnote{A string $\alpha  \in (\Sigma \cup V)^*$ is said
a {\it right sentential form} 
for a grammar $G = (\Sigma, V, P, S)$ if, and only if, 
exists a rightmost derivation from the start symbol $S$ to $\alpha$
}
between \verb|'TYPE'| and 
\verb|';'| is stored in \verb|$s|. If the string of tokens \verb|$s| 
in $\Sigma^*$ conforms to the syntax of an enumerated type
\begin{center}
\begin{tabular}{p{6.4cm}}
\begin{verbatim}
/^TYPE ID = \( ID ( , ID )* \) ;$/
\end{verbatim}
\end{tabular}
\end{center}
\noindent we set the parsing action to reduce by the production 
$id\_list \rightarrow ID$ for the two conflictive tokens \verb|','|
and \verb|')'|. Otherwise the input represents a range type.

In most cases, as occurs in this example, the nested parsing step
required to decide which action must be taken
can be accomplished
through a simple regular pattern. Nested parsing is extraordinarily
eased by the fact that Perl 5.10 standard regular patterns 
permit the description of context free languages.
Even more, modules like \verb|Regexp::Grammar| \cite{conway} bring 
Perl 6 \cite{perl6} regular patterns to Perl 5, extending
Perl 5 regular patterns beyond the capabilities of Packrat parsing \cite{ford}.

The call \verb|YYLookBothWays|$(a,b)$ 
returns
the string that is the concatenation of the transition tokens in the {\it stack} after token $a$
followed by the tokens in the {\it unexpended input} before token $b$. It does not alter the
current parsing position.

To be more precise, suppose that at the time of the call the pair
\begin{equation}
(s_0 X_1 s_1 X_2 s_2 \cdots X_m s_m, a_i a_{i+1} \cdots a_n \$ )
\end{equation}
is the {\it configuration} of the LR parser. Here $X_j \in \Sigma \cup V$ is a token or a syntactic variable,
$a_k \in \Sigma$ are tokens and $s_i$ are the states of the LR automata.  Remember that 
the equation $\delta(s_k, X_{k+1}) = s_{k+1}$ for each $k$ is hold by any configuration, 
$\delta$ being the transition function.
%$ \left \{ w \in \Sigma^* :  \exists S  \deriv{} \alpha A w \Longrightarrow \alpha \beta w \right \}$
This configuration corresponds to the right sentential form 
\begin{equation}
X_1 X_2 \cdots X_m, a_i a_{i+1} \cdots a_n \$ 
\end{equation}
which must be in the rightmost derivation from the grammar start symbol being built.
The call \verb|YYLookBothWays(|$a, b$\verb|)| returns
\begin{equation}
X_j \cdots X_m a_i a_{i+1} \cdots a_s \$ 
\end{equation}
where $j$ is the shallowest index in the stack such that $X_j = a$ and $s$ is the nearest
index in the unexpended input such that $a_s = b$.

%\input{cplusplus.tex}
\section{Conflicts Requiring Unlimited Look-ahead}
\label{section:xsx}

The following unambiguous grammar can not be parsed by any LL(k) nor LR(k), whatever
the value of \verb|k|,  nor for packrat parsing algorithms \cite{ford}.

\begin{center}
\begin{tabular}{p{2.8cm}}
\begin{verbatim}
%%
S: x S x | x  ;
%%
\end{verbatim}
\end{tabular}
\end{center}
Though it is straighforward to find equivalent LL(1) and LR(1) grammars (the language 
is even regular: \verb|/x(xx)*/|), both
GLR \cite{tomita2} and Backtrack LR parsers \cite{merrill} for this grammar will suffer 
of a  potentially exponential complexity in the input size.
The unlimited number of look-aheads required to decide if the current \verb|x| is in the middle
of the sentence, leads to an increase
in the number of branches to explore. 
The challenge 
is to make the parser work {\it without changing} the grammar. 
Figure \ref{figure:nopackrat} shows a solution using 
PPCR:

\begin{figure}[hbt]
\begin{center}
\begin{tabular}{p{11.9cm}}
\begin{verbatim}
%conflict isInTheMiddle {
  my $nxs = $self->YYSymbolStack(0,-1, 'x'); # number of visited 'x's 
  my $nxr = (unexpendedInput() =~ tr/x//);   # number of remaining 'x's

  if ($nxs == $nxr+1) { $self->YYSetReduce('x', ':MIDx' ) }
  else { $self->YYSetShift('x') }
}

%%
S:
     x  %PREC isInTheMiddle S x
  |  %name :MIDx
     x  %PREC isInTheMiddle ;
\end{verbatim}
\end{tabular}
\end{center}
\caption{Parsing a Non LL(k) nor LR(k) nor packrat grammar}
\label{figure:nopackrat}
\end{figure}


A call \verb|$self->YYSymbolStack(|$a, b, [filter]$\verb|)| returns 
the list of symbols associated with the parser stack states 
between $a$ and $b$. A negative value of $a$ or $b$ refers to the position
from the end of the list.
Thus, a call like \verb|$self|\verb|->| \verb|YYSymbolStack(0,-1)| returns the whole list 
of symbols in the parsing stack. The optional $filter$ argument can be a string, a closure\footnote{
A closure is a first-class function with free variables that are bound in the lexical environment
}
or a regular pattern. When it is a pattern the sublist for which the 
pattern matches is selected. If it is a closure, it returns the sublist 
of symbols for which the evaluation of the code is true.
If it is a string, as in \verb|$self->YYSymbolStack(0,-1, 'x')|, the sublist of symbols
equal to the string is selected.
Since the assignment \verb|$nxs = $self->YYSymbolStack(0,-1, 'x')| is evaluated
in a scalar context, the length of the resulting sublist is stored in the 
variable \verb|$nxs|. 
The copy of the unexpended input - returned by the call to \verb|unexpendedInput()| -
is then scanned for \verb|'x'|s and its number is stored in \verb|$nxr|.
When \verb|$nxs| equals \verb|$nxr +1| it is time to reduce
by $S \rightarrow x$.
It may seem that this solution
cannot be generalized when \verb|'x'| is an arbitrary
grammar. Remember however that Perl 5.10 regular patterns
can parse any context free grammar \cite{conway}.

We can now compile the former program \verb|nopackratSolved.eyp| to generate
a script \verb|nopackratSolved.pl| containing the parser.
When executed with input \verb|xxx|
it outputs
a description of the abstract syntax tree:
\begin{center}
\begin{tabular}{p{9.9cm}}
\begin{verbatim}
$ eyapp -TC -o nopackratSolved.pl nopackratSolved.eyp 
$ ./nopackratSolved.pl -t -i -c 'xxx'
S(TERMINAL[x],S(TERMINAL[x]),TERMINAL[x])
\end{verbatim}
\end{tabular}
\end{center}

Option \verb|-T| instructs \verb|eyapp| to automatically 
insert semantic actions to produce a data structure representing
the abstract syntax tree. Option \verb|-C| tells the compiler to produce 
an executable (by default it produces a class containing the parser).
Eyapp provides default lexical analyzer, error handler and main subroutines 
for the generated program.
The default \verb|main| subroutine admits several command line options, like:
{\tt \ -t} (print the AST),
{\tt \ -i} (print the semantic values of the tokens) 
and
{\tt \ -c} {\tt arg} (take the input from \verb|arg|).

\section{Conclusions}
\label{section:conclusion}

The strategy presented in this paper
extends the classic yacc precedence mechanisms
with new dynamic conflict resolution mechanisms.
These new mechanisms provide ways to resolve conflicts
that can not be solved using static precedences.
They also provides 
finer control over the conflict resolution process
than existing alternatives, like GLR and backtracking LR.
There are no limitations
to PPCR parsing, since the conflict handler is implemented in a universal language and it then 
can resort to any kind of nested parsing algorithm. 
The conflict resolution mechanisms presented 
here can be introduced in any LR parsing tools,
since they are independent of the implementation language and
the language used for the expression
of the semantic actions.  
One disadvantage of PPCR is that it requires some knowledge of LR parsing.
Though the solution may be more efficient, it certainly involves more programmer work 
than branching methods like GLR or backtracking LR.
%It must be applied only when none of the other options (static precedences,
%grammar modification, backtracking or GLR) produce satisfactory solutions.
%Quoting a common Perl saying, the goal of PPCR for yacc-like parsers is 
%``{\it to make the easy things easy, and the difficult things possible}".


\section*{Acknowledgments}
%
This work has been supported by the \textsc{ec} (\textsc{FEDER}) and
the Spanish Ministry of Science and Innovation inside the 'Plan Nacional de
\textsc{i+d}+i' with the contract number \textsc{tin2008-06491-c04-02}.
%
It has also been supported by the Canary Government project number
\textsc{pi2007/015}.
%

\begin{thebibliography}{99}

\bibitem{Johnsonyacc}
Steven~C. Johnson.
\newblock Yacc: Yet another compiler compiler.
\newblock In {\em {UNIX} Programmer's Manual}, volume~2, pages 353--387. Holt,
  Reinhart, and Winston, 1979.
\newblock AT\&T Bell Laboratories Technical Report July 31, 1978.

\bibitem{merrill}
\newblock Gary H. Merrill. 
\newblock Parsing Non-LK(  k  ) Grammars with Yacc. 
\newblock Software, Practice and  Experience 23(8): 829-850 (1993).

\bibitem{c} 
Kernighan \& Ritchie.
\newblock {\em The C Programming Language.} 
\newblock {Prentice Hall.}

\bibitem{tomita2}
Tomita, M. (1990).
\newblock {The Generalized LR Parser/Compiler - Version 8.4.}
\newblock In {\em Proceedings of International Conference on Computational
Linguistics (COLING'90)}, pages 59--63, Helsinki, Finland.

\bibitem{elkhound}
Mcpeak, Scott. September 2004.
\newblock {Elkhound: A Fast, Practical GLR Parser Generator}.
\newblock {\verb|http://scottmcpeak.com/elkhound/|}

\bibitem{kelbt}
Adrian D. Thurston and James R. Cordy.
\newblock {A Backtracking LR Algorithm for Parsing Ambiguous Context-Dependent Languages.}
\newblock {2006 Conference of the Centre for Advanced Studies on Collaborative Research (CASCON 2006), pp. 39-53, Toronto, October 2006.}

\bibitem{bison}
Charles Donnelly and Richard~M. Stallman.
\newblock {Bison: the yacc-com\-pat\-i\-ble parser generator.}
\newblock {Technical report, {F}ree {S}oftware {F}oundation, 675 Mass Ave,
Cambridge, MA 02139, Tel: (617) 876-3296, 1988.}

%\bibitem{c++}
%B. Stroustrup.
%\newblock {\it The C++ Programming Language}.
%\newblock Addison Wesley, 1986.

\bibitem{stroustrup}
Margaret A. Ellis and Bjarne Stroustrup.
\newblock {\em The Annotated C++ Reference Manual}.
\newblock {Addison-Wesley, Reading, Massachussetts, 1990.}

\bibitem{Rodriguez:Leon}
Rodr\'iguez-Le\'on Casiano.
\newblock {\tt Parse::Eyapp} Manuals. 2007.
\newblock \\CPAN: {\tt http://search.cpan.org/dist/Parse-Eyapp/ } 
\newblock \\google-code: {\tt http://code.google.com/p/parse-eyapp/ } 

\bibitem{Wall:Perl}
Wall, L., Christiansen, T., Schwartz, R. (1996).
\newblock {\em Programming Perl.}
\newblock {O'Reilly \&~Associates.}

\bibitem{perl6}
Allison Randal, Dan Sugalski, Leopold Totsch.
\newblock {\em Perl 6 and Parrot Essentials.}
\newblock {O'Reilly Media. June 2004.}

\bibitem{hudak}
Hudak, P.
\newblock {Modular Domain Specific Languages and Tools.}
\newblock {ICSR '98: Proceedings of the 5th International Conference on Software Reuse.}
\newblock {IEEE Computer Society. Pages 134-142, June 1998.}

\bibitem{ISO:1990:EPI}
ISO.
\newblock {Extended Pascal ISO 10206:1990.}\\
\newblock {\tt http://www.standardpascal.org/iso10206.txt}.

\bibitem{ford}
Bryan Ford.
\newblock Functional Pearl: Packrat Parsing: Simple, Powerful, Lazy, Linear Time.\\
\newblock {\tt http://pdos.csail.mit.edu/~baford/packrat/icfp02/packrat-icfp02.pdf}
        (2002).

\bibitem{conway}
Damian Conway.
\newblock {Regexp::Grammars. Add grammatical parsing features to Perl 5.10 regexes.}
\newblock {\tt http://search.cpan.org/dist/Regexp-Grammars/}.

%\bibitem{peg} 
%\newblock Wikipedia
%\newblock Parsing expression grammar\\ 
%\newblock {\tt http://en.wikipedia.org/wiki/Parsing\_expression\_grammar}

%\bibitem{warth}
%Warth, Douglas and Millstein.
%\newblock Packrat Parsers Can Support Left Recursion. 
%\newblock PEPM '08.  January 2008. {\tt http://www.vpri.org/pdf/tr2007002\_packrat.pdf}. 

%\bibitem{denny}
%Denny, Joel E. and Malloy, Brian A.
%\newblock IELR(1): practical LR(1) parser tables for non-LR(1) grammars with conflict resolution.
%\newblock SAC '08: Proceedings of the 2008 ACM symposium on Applied computing. 2008 240-245, ACM.

%\bibitem{bowers}
%\newblock Eric Bouwers, Martin Bravenboer and  Eelco Visser.  
%\newblock Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking.
%\newblock Electronic Notes in Theoretical Computer Science (ENTCS). Elsevier Science Publishers.  Volume 203 ,  Issue 2  (April 2008) Pages 85-101  

%\bibitem{schroedinger}
%John Aycock and R. Nigel Horspool.
%\newblock Schroedinger's token.
%\textit{Software---Practice and Experience} July 2001;  % Journal title and year;
%                           % --here we do use caps for important words
%\textbf{31}(8):803--814.              % Volume, issue, pages.

\end{thebibliography}
\end{document}

